/**
 * 剑指 Offer 11. 旋转数组的最小数字
 * https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
 */

/**
 * @param {number[]} numbers
 * @return {number}
 */
function minArray(numbers) {
  let left = 0;
  let right = numbers.length - 1;
  while (left < right) {
    const middle = (left + right) >> 1;
    const leftVal = numbers[left];
    const rightVal = numbers[right];
    const middleVal = numbers[middle];
    if (middleVal > rightVal) {
      left = middle + 1;
    } else if (middleVal === rightVal) {
      if (middleVal > leftVal) {
        right = middle - 1;
      } else if (middleVal < leftVal) {
        left += 1;
        right = middle;
      } else {
        left += 1;
      }
    } else {
      right = middle;
    }
  }
  return numbers[left];
}

console.log(minArray([3, 4, 5, 1, 2]) === 1);
console.log(minArray([2, 2, 2, 0, 1]) === 0);
console.log(minArray([0, 2, 2, 0, 0]) === 0);
console.log(minArray([2, 2, 2, 0, 0]) === 0);
console.log(minArray([1, 3, 5]) === 1);
